What is Clustering?

Why cluster in finance?

1. Quantitative analysts may look for historical analogues to current events, a task that involves developing a numerical taxonomy of events.
2. Portfolio managers often cluster securities with respect to a variety of features, to derive relative values among peers.
3. Risk managers are keen to avoid the concentration of risks in securities that share common traits.
4. Traders wish to understand flows affecting a set of securities, to determine whether a rally or sell-off is idiosyncratic to a particular security, or affects a category shared by a multiplicity of securities.

In tackling these problems, we use the notions of distance we studied in previous weeks

Proximity matrix

• Consider a data matrix $X$, of order $N \times F$, where $N$ is the number of objects and $F$ is the number of features.
• We use the $F$ features to compute the proximity between the N objects, as represented by an $N \times N$ matrix.
• The proximity measure can indicate either similarity (e.g., correlation, mutual information) or dissimilarity (e.g., a distance metric).
• It is convenient but not strictly necessary that dissimilarity measures satisfy the conditions of a metric: nonnegativity, symmetry and triangle inequality
• The proximity matrix can be represented as an undirected graph where the weights are a function of the similarity (the more similar, the greater the weight) or dissimilarity (the more dissimilar, the smaller the weight).
• Then the clustering problem is equivalent to breaking the graph into connected components (disjoint connected subgraphs), one for each cluster.
• When forming the proximity matrix, it is a good idea to standardize the input data, to prevent that one feature’s scale dominates over the rest.

Cluster FIFA 20 players

Clustering algorithms

There are two main classes of clustering algorithms: partitional and hierarchical

• Partitional techniques create a one-level (un-nested) partitioning of the objects (each object belongs to one cluster, and to one cluster only) simultaneously.
• Hierarchical techniques produce a nested sequence of partitions, with a single, all-inclusive cluster at the top and singleton clusters of individual points at the bottom. Hierarchical clustering algorithms can be divisive (top-down) or agglomerative (bottom-up).

A partitional algorithm: K-means

• K-Means is a vector quantization model.

Statistical thinking

It attempts to split the samples (rows) of $X$ into a predetermined number of clusters $K$

Algorithmic thinking

• Step 1: Initialize a random set of K centroids

• Step 2: Assign each sample to one cluster such that the within-cluster variance is minimised

• Step 3: Update K centroids based on the clusters from Step 2

• Step 4: Repeat steps 2 and 3 until convergence]

A partitional algorithm: K-mean

fungible::monte(seed = 123, nvar = 2, nclus = 3, clus.size = c(1000, 1000, 1000), eta2 = c(0.70, 0.30)) -> dat
dat1 <- as_tibble(dat$data)
kmeansObj <- kmeans(dat1, centers = 3)

factoextra::fviz_cluster(kmeansObj, data = dat1)

A few considerations

• K-Means assumes that the clusters are convex, isotropic, and with similar variance
• Features should be standardized prior to clustering
• Other algorithms may perform better when clusters are elongated or irregular
• Within-cluster variance is not a normalized metric
• Curse of dimensionality: When $X$ has many columns, variances are inflated, and outcomes may be biased.
• One solution is to apply a dimensionality reduction technique (e.g., PCA) prior to clustering
• K-Means will always converge, however the outcome may be a local minimum
• One solution is to run multiple instances in parallel, with different seed centroid

A Hierarchical Algorithm: Agglomerative Clustering

Algorithmic thinking

• Step 1: Apply a distance metric to $X$
• Step 2: Combine into a cluster the pair with lowest distance. The pair can be composed of two items, two clusters, or one item and a cluster]
• Step 3: Reduce the distance matrix
  • Remove the 2 rows and columns associated with the pair
  • Apply a linkage criterion to determine the distance between the new cluster and the rest of objects, e.g.: -Single linkage: minimum distance to any object in the pair
  • Complete linkage: maximum distance to any object in the pair]{.small}
• Step 4: Repeat steps 2 and 3 until the distance matrix has been reduced to only one object

Dendrogram

• A dendrogram is a tree graph that displays the hierarchical composition of the clusters
• The y-axis indicates the distance between the two objects that form a new cluster
• A linkage matrix characterizes a dendrogram
  • For N items, a linkage matrix has N-1 rows (one row per cluster)
  • Three columns:
    • Integer identifying object 1
    • Integer identifying object 2
    • Distance between objects 1 and 2 (based on linkage criterion)
• pretty dendrograms = ggdendro package

A few considerations

• Hierarchical algorithms can handle clusters that are non-convex, anisotropic, with unequal variance
  • This includes clusters within clusters
• Hierarchical algorithms allow connectivity constraints
  • Connectivity constraints cluster together only adjacent points. This links together points even if the centroid is not part of the cluster
• However, hierarchical algorithms may not handle properly elongated blobs
  • One solution is to orthogonalize the features (e.g., PCA without dimensionality reduction) prior to clustering
• The appropriate linkage method can be chosen via cross-validation, or cophenetic correlation

Example of hierarchical clustering

set.seed(12345)
f1 <- rnorm(45, rep(1:3, each = 15), 0.2)
f2 <- rnorm(45, rep(c(1, 2, 1), each = 15), 0.2)
tibble(x = f1, y = f2, obs = 1:45) -> dat

dat %>% 
  ggplot(aes(x = x, y = y)) +
  geom_point(colour = 'pink') +
  geom_label(aes(label = obs)) 

hClustering <- dat %>% 
  dist() %>% 
  hclust(method = 'single') #<<

ggdendrogram(hClustering)

Types of clustering

• Depending on the definition of cluster, we can distinguish several types of clustering algorithms, including the following:

1. Connectivity: This clustering is based on distance connectivity, like hierarchical clustering. Finance example =
2. Centroids: These algorithms perform a vector quantization, like k-means, Finance example = @Prado2018.
3. Distribution: Clusters are formed using statistical distributions
4. Density: These algorithms search for connected dense regions in the data space. Examples include DBSCAN and OPTICS.
5. Subspace: Clusters are modeled on two dimensions, features and observations. An example is biclustering/coclustering. For instance, they can help identify similarities in subsets of instruments and time periods

Cluster scoring

• In order to determine the optimal number of clusters, we first need to define a function that scores the output of a scoring algorithm
• In general, there are two types of clustering scoring functions:

1. External: those that require ground-truth labels
2. Internal: those that don’t require it

• Because clustering is an unsupervised learning problem, internal scores are more natural. Three of the most used internal scoring functions are:

1. Calinski-Harabasz index (or variance ratio) direct method
2. Gap statistics Statistical method
3. Silhouette scores direct method

How many blobs are there?

f2c3<-monte(seed = 123,nvar = 2,nclus = 3,clus.size = c(1000,1000,1000),eta2 = c(0.9,0.9))[['data']] %>% as.tibble()
f2c3 %>% ggplot(aes(x=V2,y=V3)) + geom_point(colour='pink')

Calinski-Harabasz index (or variance ratio)

• The Calinski-Harabasz index of a clustering is the ratio of the between-cluster variance (which is essentially the variance of all the cluster centroids from the dataset’s grand centroid) to the total within-cluster variance (basically, the average WSS of the clusters in the clustering).
• For a given dataset, the total sum of squares (TSS) is the squared distance of all the data points from the dataset’s centroid.
• The TSS is independent of the clustering.
• If WSS(k) is the total WSS of a clustering with k clusters, then the between sum of squares BSS(k) of the clustering is given by BSS(k) = TSS - WSS(k).
• WSS(k) measures how close the points in a cluster are to each other.

Calinski-Harabasz index (or variance ratio)

• BSS(k) measures how far apart the clusters are from each other.
• A good clustering has a small WSS(k) and a large BSS(k).
• The within-cluster variance W is given by WSS(k)/(n-k), where n is the number of points in the dataset.
• The between-cluster variance B is given by BSS(k)/(k-1).
• The within-cluster variance will decrease as k increases; the rate of decrease should slow down past the optimal k.
• The between-cluster variance will increase as k, but the rate of increase should slow down past the optimal k.
• So in theory, the ratio of B to W should be maximized at the optimal